package q886_possibleBipartition;

import CommonClass.UF;

import java.util.ArrayList;
import java.util.List;

public class Solution_3 {
    /*
    并查集，同样的先构建一个g
    然后对于每一个人，我们先遍历他所有不喜欢的人，并将这些不喜欢的人都进行连接
    如果我们发现过程中出现了当前人和不喜欢的人出现在了同一个簇中
    也就说明不能成功
     */
    public boolean possibleBipartition(int n, int[][] dislikes) {
        UF uf = new UF(n + 1);
        List<Integer>[] g = new List[n + 1];
        for (int i = 0; i <= n; ++i) {
            g[i] = new ArrayList<>();
        }
        for (int[] p : dislikes) {
            g[p[0]].add(p[1]);
            g[p[1]].add(p[0]);
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < g[i].size(); ++j) {
                uf.union(g[i].get(0), g[i].get(j));
                if (uf.isConnected(i, g[i].get(j))) {
                    return false;
                }
            }
        }
        return true;
    }

}
